On Computable Numbers 论文
概述
阿兰·图灵于1936年发表的划时代论文，首次精确定义了"计算"的数学概念（图灵机），证明了停机问题不可判定，否定回答了判定问题 (Entscheidungsproblem)，并构造了通用图灵机预言了可编程计算机。被公认为计算机科学的"创世文档"。
关键内容
论文信息
| 字段 | 内容 |
|---|---|
| 标题 | On 可计算数</td>
</tr>
<tr>
<td><strong>作者</strong></td>
<td>[[阿兰·图灵</td>
</tr>
<tr>
<td><strong>提交时间</strong></td>
<td>1936年5月28日</td>
</tr>
<tr>
<td><strong>正式出版</strong></td>
<td>1937年，附勘误与附录</td>
</tr>
<tr>
<td><strong>发表期刊</strong></td>
<td>Proceedings of the London Mathematical Society, Series 2, Volume 42, pp. 230–265</td>
</tr>
<tr>
<td><strong>作者当时身份</strong></td>
<td>剑桥大学国王学院研究员，年仅24岁</td>
</tr>
</tbody>
</table>
<h3 id="_4">四大核心贡献</h3>
<ol>
<li>
<p><strong>[[图灵机定义：通过对人类计算员行为的忠实抽象（有限符号、有限状态、每步一格），给出了有史以来第一个数学上完全精确的"计算"定义。Godel 本人评价为"哲学上不可能设置得更令人满意"。
通用图灵机：证明存在一台能模拟任意图灵机的机器——在概念层面预言了可编程计算机的出现，比 ENIAC（1946年）早10年，比 von Neumann 存储程序架构（1945年）早9年。 停机问题不可判定：通过反证法和对角化论证，证明不存在算法能判定任意程序是否停机。这是第一个被严格证明不可判定的具体问题，开创了不可判定性理论的整个领域。 判定问题 (Entscheidungsproblem)的否定回答：由停机问题的不可判定性推导出 Hilbert 判定问题不可解，与 Godel 不完备定理一起彻底终结了 Hilbert 形式化纲领。 附录：与 Church λ 演算的等价性Turing 在附录中证明了图灵可计算性与 λ 可定义性的完全等价，这一结果连同与 Godel 递归函数、Post 产生式系统、Markov 算法等的等价性，共同构成了Church-Turing 论题的经验基础。 历史意义很少有学术论文能够同时： - 解决了一个著名的悬而未决的数学问题（判定问题） - 创立了一个全新的学科（计算理论） - 发明了一个至今仍在使用的核心概念（图灵机） - 预言了一种尚未出现的技术（可编程计算机） Turing 的这篇论文做到了以上所有。在人类思想史上，很难找到第二篇单独的论文具有如此多维度的深远影响。 来源
相关
|